package com.atguigu.tree.haffmancode;



import java.util.*;

/**
 * @author RuiKnag
 * @create 2021-05-19-17:11
 */
public class haffmanCodeDemo {
    public static void main(String[] args) {
        String str="i like like like java do you like a java";

        byte[] bytes = str.getBytes();
        byte[] haffmanZip = haffmanZip(bytes);
        System.out.println("haffmanZip = " + Arrays.toString(haffmanZip));
        StringBuilder builder = bytesToString(haffmanZip);
        System.out.println("solve = " + builder);
        byte[] decode = decode(haffmanCodeMap, builder);
        System.out.println("原来的字符串 = " + new String(decode));
       /* System.out.println("求一下字节数组的长度");
        System.out.println(bytes.length);
        //将创建的node对象的data和weight放入到列表中
        ArrayList<Node> node = getNode(bytes);
        System.out.println("node = " + node);
        //创建哈夫曼树，得到我们根节点是哪一个
        Node root = createHaffman(node);
        //遍历根节点得到我们的树
        prePost(root);
        //创建我们的赫夫曼编码表
        Map<Byte, String> codes = getCodes(root);
        //展示我们的赫夫曼编码表
        System.out.println("赫夫曼编码表"+codes);
        System.out.println("赫夫曼编码表"+haffmanCodeMap);
        //测试我们的字符串对应的哈夫曼编码结果
        byte[] zip = zip(bytes, haffmanCodeMap);
        System.out.println(Arrays.toString(zip));*/

    }
    //前序遍历哈夫曼树
    public static void prePost(Node root){
        if(root==null){
            System.out.println("空树");
        }else{
            root.perList();
        }
    }
    //构建哈夫曼树
    public static ArrayList<Node> getNode(byte[] bytes) {
        //统计字节频数
        Map<Byte, Integer> map = new HashMap<>();
        for (int i = 0; i < bytes.length; i++) {
            Integer count = map.get(bytes[i]);
            if (count == null) {
                map.put(bytes[i], 1);
            } else {
                map.put(bytes[i], count + 1);
            }
        }
        //将对应的字节频率放到Node的列表中，为下一步构建哈夫曼树创造条件
        ArrayList<Node> nodes = new ArrayList<>();
        //对map进行遍历
        for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }
    //创建哈夫曼树
    public static Node createHaffman(ArrayList<Node> nodes){
        //将nodes装换为哈夫曼树
        while (nodes.size()>1){
            //对nodes进行从小到达的排序
            Collections.sort(nodes);
            //取出最小的两个节点
            Node leftNode = nodes.get(0);
            Node rightNOde = nodes.get(1);
            Node parent = new Node(leftNode.weight + rightNOde.weight);
            //将这两个节点与父节点相连接
            parent.left=leftNode;
            parent.right=rightNOde;
            //删除node里面最小的两个节点
            nodes.remove(leftNode);
            nodes.remove(rightNOde);
            //添加parent节点
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //重载一下
    public static Map<Byte,String> getCodes(Node root){
        if(root==null){
            System.out.println("空树");
        }else{
            getCodes(root.left,"1",sb);
            getCodes(root.right,"0",sb);
        }
        return haffmanCodeMap;
    }
    //生成赫夫曼树对应的赫夫曼编码表
    /*
    * 1.将哈夫曼编码表存储在map中Map<Byte,String>
    * 2.生成赫夫曼编码时，需要去拼接路径,定义一个StringBuilder存储某个叶子节点
    * */

    static Map<Byte,String> haffmanCodeMap=new HashMap<>();
    static StringBuilder sb=new StringBuilder();
    public static void getCodes(Node node,String code,StringBuilder stringBuilder){
        StringBuilder builder = new StringBuilder(stringBuilder);
        builder.append(code);
        //判断我们的节点是否为空
        if(node!=null){
            //判断我们是否达到了叶子节点
            if(node.data==null){
                //递归处理。递归左右子树
                getCodes(node.left,"0",builder);
                getCodes(node.right,"1",builder);
            }else{
                haffmanCodeMap.put(node.data,builder.toString());
            }
        }
    }
    //编写一个方法，将一个字符串对应的byte[]数组，通过生成的赫夫曼编码，返回一给赫夫曼编码压缩成byte[]
    private static byte[] zip(byte[] bytes,Map<Byte,String> haffmanCodeMap){
        //利用StringBuilder存储我们字符串对应的haffmancode值
        StringBuilder builder = new StringBuilder();
        for (byte b:bytes){
            builder.append(haffmanCodeMap.get(b));
        }
        //我们在存储的时候放到一个新的byte数组里面
        //计算该数组的长度
        int len=(builder.length()+7)/8;
        byte[] haffmanByte = new byte[len];
        int index=0;
        //将builder的内容放到数组里面
        for (int i = 0; i < builder.length(); i+=8) {
            String str="";
            if(i+8>builder.length()){
                str=builder.substring(i,builder.length());
            }else {
                str=builder.substring(i,i+8);
            }
            haffmanByte[index++]= (byte) Integer.parseInt(str,2);
        }
        return haffmanByte;
    }
    //使用一个方法将前面的方法封装起来,相当于压缩
    public static byte[] haffmanZip(byte[] bytes){
        //将我们输入的字符串的byte数组，获取每个字母的频率，并放到我们节点中，存放到一个ArrayList数组中
        ArrayList<Node> nodes = getNode(bytes);
        //构建我们的节点对应的哈夫曼树,生成我们的根节点
        Node haffman = createHaffman(nodes);
        //构建我们每一个字母对应的哈夫曼编码,将得到的数据存放到map中
        Map<Byte, String> haffmancodes = getCodes(haffman);
        //得到我们新编码之后的byte数组
        byte[] zip = zip(bytes, haffmancodes);
        return zip;
    }

    //完成解压
    /*
    * 将haffmanZip = [60, 46, -36, 46, -36, 46, -35, 5, -115, 23, -86, -45, -62, -19, -114, -126, 24]重新写成二进制形式
    * 赫夫曼编码对应着二进制形式，重新生成对应的String
    *
    * */
    public static StringBuilder bytesToString(byte[] bytes){
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < bytes.length; i++) {
            byte b=bytes[i];
            boolean flag=(i==bytes.length-1);
            builder.append(byteToBitString(!flag, b));

        }
        System.out.println(builder.length());
        System.out.println(builder);
        String res = builder.toString();
        return builder;
    }
    public static byte[] decode(Map<Byte, String> haffmanCodeMap,StringBuilder builder){
        //我们将Map里面的键值对反过来
        Map<String, Byte> map = new HashMap<>();
        for(Map.Entry<Byte, String> entry:haffmanCodeMap.entrySet()){
            map.put(entry.getValue(),entry.getKey());
        }
        int index=0;
        //先用list存放我们的结果
        List<Byte> list = new ArrayList<>();
        int len=1;
        while (index<builder.length()){

            String str=builder.substring(index,index+len);
            Byte aByte = map.get(str);
            if(aByte==null){
                len++;
            }else{
                list.add(aByte);
                index+=len;
                len=1;
            }
        }
        //将列表中的值添加到byte数组中
        byte[] res = new byte[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }

        return res;
    }
    /**
     * 将一个byte 转成一个二进制的字符串, 如果看不懂，可以参考我讲的Java基础 二进制的原码，反码，补码
     * @param b 传入的 byte
     * @param flag 标志是否需要补高位如果是true ，表示需要补高位，如果是false表示不补, 如果是最后一个字节，无需补高位
     * @return 是该b 对应的二进制的字符串，（注意是按补码返回）
     */
    private static String byteToBitString(boolean flag, byte b) {
        //使用变量保存 b
        int temp = b; //将 b 转成 int
        //如果是正数我们还存在补高位
        if(flag) {
            temp |= 256; //按位与 256  1 0000 0000  | 0000 0001 => 1 0000 0001
        }
        String str = Integer.toBinaryString(temp); //返回的是temp对应的二进制的补码
        if(flag) {
            return str.substring(str.length() - 8);
        } else {
            return str;
        }
    }


}
//存放数据本身
class Node implements Comparable<Node> {
    Byte data;//存储字符本身
    int weight;//字符出现次数
    Node left;
    Node right;

    public Node(int weight) {
        this.weight = weight;
    }

    public Node(Byte data, int weight) {
        this.data = data;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", weight=" + weight +
                '}';
    }
    //前序遍历
    public void perList(){
        System.out.println(this);
        if(this.left!=null){
            this.left.perList();
        }
        if(this.right!=null){
            this.right.perList();
        }
    }

    @Override
    public int compareTo(Node o) {
        return this.weight-o.weight;
    }
}
